package com.aqie.easy.tree;

import com.aqie.easy.structure.TreeNode;

import java.util.LinkedList;

/**
 * 671 二叉树中第二小的节点  todo
 */
public class FindSecondMinimumValue {

    /**
     * 1, 定义两个变量存放 第一 第二小的值 1ms
     */
    int one = -2;   //第一小
    int two = -1;   //第二小

    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        helper(root);
        if (two == -2)
            return -1;
        return two;
    }

    private void helper(TreeNode root) {
        if (root == null) return;

        if (one == -2) {
            one = root.val;
        } else if (two == -1) {
            if (root.val > one)
                two = root.val;
            else if (root.val != one) {
                two = one;
                one = root.val;
            }
        }
        if (root.val < one) {
            two = one;
            one = root.val;
        } else if (root.val > one && root.val < two) {
            two = root.val;
        }
        helper(root.left);
        helper(root.right);

    }


    /**
     * 2, 1ms
     * @param root
     * @return
     */
    public int FindSecondMinimumValue(TreeNode root) {
        if(root == null) return -1;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int rootValue = root.val;
        int result=rootValue;
        while(!queue.isEmpty())
        {
            TreeNode node = queue.poll();

            if (node.left != null)
            {
                if (node.left.val != node.val && node.right.val != node.val)
                {
                    result = Math.min(node.left.val, node.right.val);
                    break;   //注意，只能在两个节点同时都不等于父节点时才能break，否则后面可能会出现比当前某一节点更小的值
                }
                else if (node.left.val == node.val)
                {
                    if (result == rootValue)
                        result = node.right.val;
                    else if(node.right.val> rootValue)
                        result = Math.min(result, node.right.val);
                }
                else if (node.right.val == node.val)
                {
                    if (result == rootValue)
                        result = node.left.val;
                    else if(node.left.val > rootValue)
                        result = Math.min(result, node.left.val);
                }
                queue.add(node.left);
                queue.add(node.right);
            }

        }
        if(result ==rootValue)
            return -1;
        else return result;
    }


}

